package com.sicheng.algorithm.string;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/1/26 18:51
 */
public class 最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = {"aac", "aca", "aa"};
        String prefix = longestCommonPrefix(strs);
        System.out.println(prefix);
        System.out.println(prefix.substring(0, 0));
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 1)
            return strs[0];
        char[] chars = strs[0].toCharArray();
        int end = chars.length - 1;
        if (end < 0)
            return "";
        int minLen = chars.length;
        for (int i = 1; i < strs.length; i++) {
            String str = strs[i];
            if (str.length() == 0)
                return "";
            minLen = Math.min(minLen, str.length());
            int j;
            for (j = 0; j < minLen; j++) {
                if (chars[j] != str.charAt(j)) {
                    break;
                }
            }
            if (j - 1 < end)
                end = j - 1;
        }

        return strs[0].substring(0, end + 1);
    }
}
